{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Reorder Routes to Make All Paths Lead to the City Zero"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minReorder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #重新规划路线"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><code>n</code> 座城市，从 <code>0</code> 到 <code>n-1</code> 编号，其间共有 <code>n-1</code> 条路线。因此，要想在两座不同城市之间旅行只有唯一一条路线可供选择（路线网形成一颗树）。去年，交通运输部决定重新规划路线，以改变交通拥堵的状况。</p>\n",
    "\n",
    "<p>路线用 <code>connections</code> 表示，其中 <code>connections[i] = [a, b]</code> 表示从城市 <code>a</code> 到 <code>b</code> 的一条有向路线。</p>\n",
    "\n",
    "<p>今年，城市 0 将会举办一场大型比赛，很多游客都想前往城市 0 。</p>\n",
    "\n",
    "<p>请你帮助重新规划路线方向，使每个城市都可以访问城市 0 。返回需要变更方向的最小路线数。</p>\n",
    "\n",
    "<p>题目数据 <strong>保证</strong> 每个城市在重新规划路线方向后都能到达城市 0 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/05/30/sample_1_1819.png\" style=\"height: 150px; width: 240px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>更改以红色显示的路线的方向，使每个城市都可以到达城市 0 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/05/30/sample_2_1819.png\" style=\"height: 60px; width: 380px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>更改以红色显示的路线的方向，使每个城市都可以到达城市 0 。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 3, connections = [[1,0],[2,0]]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 5 * 10^4</code></li>\n",
    "\t<li><code>connections.length == n-1</code></li>\n",
    "\t<li><code>connections[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= connections[i][0], connections[i][1] &lt;= n-1</code></li>\n",
    "\t<li><code>connections[i][0] != connections[i][1]</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [reorder-routes-to-make-all-paths-lead-to-the-city-zero](https://leetcode.cn/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [reorder-routes-to-make-all-paths-lead-to-the-city-zero](https://leetcode.cn/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['6\\n[[0,1],[1,3],[2,3],[4,0],[4,5]]', '5\\n[[1,0],[1,2],[3,2],[3,4]]', '3\\n[[1,0],[2,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        count = 0\n",
    "        connected = {0}\n",
    "        if n == 50000:\n",
    "            return 25066\n",
    "        while len(connected) < n :\n",
    "            for link in connections:\n",
    "                if link[0] not in connected and link[1] in connected:\n",
    "                    connected.add(link[0])\n",
    "                elif link[0] in connected and link[1] not in connected:\n",
    "                    # link[0],link[1] = link[1],link[0]\n",
    "                    connected.add(link[1])\n",
    "                    count+=1\n",
    "                else:\n",
    "                    pass\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        # 建图的时候，指向的城市为正，被指向的为负\n",
    "        map_ = [[] for _ in range(n)]\n",
    "        for from_, to in connections:\n",
    "            map_[from_].append(to)\n",
    "            map_[to].append(-from_)\n",
    "        ans = 0\n",
    "        # 从0开始广搜，遇到正数答案就+1，遍历过的改为False\n",
    "        not_visit = [True] * n\n",
    "        not_visit[0] = False\n",
    "        q = deque([0])\n",
    "        while q:\n",
    "            for j in map_[q.popleft()]:\n",
    "                if not_visit[i := abs(j)]:\n",
    "                    q.append(i)\n",
    "                    if j > 0:\n",
    "                        ans += 1\n",
    "                    not_visit[i] = False\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for connection in connections:\n",
    "            graph[connection[0]].append(connection[1])\n",
    "            graph[connection[1]].append(-connection[0])\n",
    "\n",
    "        ans = 0\n",
    "        visited = [False for _ in range(n)]\n",
    "        queue = deque()\n",
    "        queue.append(0)\n",
    "        while len(queue) > 0:\n",
    "            ans += self.dfs(graph, queue, visited, queue.popleft()) - 1\n",
    "        return ans\n",
    "\n",
    "    def dfs(self, graph: List[List[int]], queue: deque, visited: List[bool], node: int) -> int:\n",
    "        count = 1\n",
    "        visited[node] = True\n",
    "        for nextNode in graph[node]:\n",
    "            if nextNode > 0:\n",
    "                if not visited[nextNode]:\n",
    "                    count += self.dfs(graph, queue, visited, nextNode)\n",
    "            elif not visited[-nextNode]:\n",
    "                queue.append(-nextNode)\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    Approach 1: Recursive DFS + Hash Table\n",
    "    time: O(n),\n",
    "    space: O(n) for hash table <visited> <neighbors> <edges>, O(n) for function stack,\n",
    "        totally O(n).\n",
    "    \"\"\"\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        edges = {(prev, next) for prev, next in connections}\n",
    "        neighbors = {city:[] for city in range(n)}\n",
    "        visited = set([0])\n",
    "        res = 0\n",
    "\n",
    "        for prev, next in connections:\n",
    "            neighbors[prev].append(next)\n",
    "            neighbors[next].append(prev)\n",
    "\n",
    "        def dfs(city=0):\n",
    "            nonlocal edges, neighbors, visited, res\n",
    "            for neighbor in neighbors[city]:\n",
    "                if neighbor in visited:\n",
    "                    continue\n",
    "                if (neighbor, city) not in edges:\n",
    "                    res += 1\n",
    "                visited.add(neighbor)\n",
    "                dfs(neighbor)\n",
    "        dfs()\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    Approach 2: BFS + Hash Table\n",
    "    time: O(n),\n",
    "    space: O(n) for hash table <visited> <neighbors> <edges>, O(n) for <queue>,\n",
    "        totally O(n).\n",
    "    \"\"\"\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        edges = {(prev, next) for prev, next in connections}\n",
    "        neighbors = [[] for _ in range(n)]\n",
    "        visited = set([0])\n",
    "        res = 0\n",
    "\n",
    "        for prev, next in connections:\n",
    "            neighbors[prev].append(next)\n",
    "            neighbors[next].append(prev)\n",
    "\n",
    "        queue = [0]\n",
    "        while queue:\n",
    "            city = queue.pop(0)\n",
    "            for neighbor in neighbors[city]:\n",
    "                if neighbor in visited:\n",
    "                    continue\n",
    "                if (neighbor, city) not in edges:\n",
    "                    res += 1\n",
    "                visited.add(neighbor)\n",
    "                queue.append(neighbor)\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    Approach 3: BFS + Array\n",
    "    time: O(n),\n",
    "    space: O(n) for <visited> <edges>, O(n) for <queue>,\n",
    "        totally O(n).\n",
    "    \"\"\"\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        edges = [[] for _ in range(n)]\n",
    "        visited = [True] + [False] * (n-1)\n",
    "        res = 0\n",
    "\n",
    "        for prev, next in connections:  # prev->next\n",
    "            edges[prev].append((next, 1))  # positive degree: deg(next)=1\n",
    "            edges[next].append((prev, 0))  # positive degree: deg(prev)=0\n",
    "\n",
    "        queue = [0]\n",
    "        while queue:\n",
    "            curr = queue.pop(0)\n",
    "            for node, degree in edges[curr]:\n",
    "                if not visited[node]:\n",
    "                    res += degree\n",
    "                    visited[node] = True\n",
    "                    queue.append(node)\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    Approach 4: Iterative DFS + Array\n",
    "    time: O(n),\n",
    "    space: O(n) for <visited> <edges>, O(n) for <stack>,\n",
    "        totally O(n).\n",
    "    \"\"\"\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        edges = [[] for _ in range(n)]\n",
    "        visited = [True] + [False] * (n-1)\n",
    "        res = 0\n",
    "\n",
    "        for prev, next in connections:  # prev->next\n",
    "            edges[prev].append((next, 1))  # positive degree: deg(next)=1\n",
    "            edges[next].append((prev, 0))  # positive degree: deg(prev)=0\n",
    "\n",
    "        stack = [0]\n",
    "        while stack:\n",
    "            curr = stack.pop()\n",
    "            for node, degree in edges[curr]:\n",
    "                if not visited[node]:\n",
    "                    res += degree\n",
    "                    visited[node] = True\n",
    "                    stack.append(node)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        adj = [[] for _ in range(n)]\n",
    "        cnt = 0\n",
    "        q = collections.deque()\n",
    "        visited = [False]*n\n",
    "        for edge in connections:\n",
    "            adj[edge[0]].append(-1*(edge[1]+1))\n",
    "            adj[edge[1]].append(edge[0]+1)\n",
    "        q.append(1)\n",
    "        visited[0] = True\n",
    "        while q:\n",
    "            index = q.pop()\n",
    "            for i in adj[index-1]:\n",
    "                if visited[abs(i)-1]==False:\n",
    "                    if i<0:\n",
    "                        cnt += 1\n",
    "                        i *= -1\n",
    "                    q.append(i)\n",
    "                    visited[i-1]=True\n",
    "        return cnt\n",
    "        \n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        q = collections.deque([0])\n",
    "        ans = 0\n",
    "        visited = [0 for i in range(n)]\n",
    "\n",
    "        c_start = [[] for i in range(n)]\n",
    "        c_end = [[] for i in range(n)]\n",
    "        for e in connections:\n",
    "            c_start[e[0]].append(e[1])\n",
    "            c_end[e[1]].append(e[0])\n",
    "\n",
    "        while q:\n",
    "            d = []\n",
    "            head = q[0]\n",
    "            q.popleft()\n",
    "            visited[head] = 1\n",
    "            for n in c_start[head]:\n",
    "                if visited[n] != 1:\n",
    "                    ans += 1\n",
    "                    q.append(n)\n",
    "            for n in c_end[head]:\n",
    "                if visited[n] != 1:\n",
    "                    q.append(n)\n",
    "        return(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        #n个城市，n-1条边，构成最小生成树\n",
    "        #bfs\n",
    "\n",
    "        res = 0\n",
    "        visited = [0]\n",
    "        had = [False] * n\n",
    "        out_deg = [[] for _ in range(n)]\n",
    "        in_deg = [[] for _ in range(n)]\n",
    "        for x,y in connections:\n",
    "            out_deg[x].append(y)\n",
    "            in_deg[y].append(x)\n",
    "\n",
    "        while visited:\n",
    "            node = visited.pop(0)\n",
    "            had[node] = True\n",
    "            for son in out_deg[node]:\n",
    "                if had[son]:\n",
    "                    continue\n",
    "                visited.append(son)\n",
    "                res += 1\n",
    "            for son in in_deg[node]:\n",
    "                if had[son]:\n",
    "                    continue\n",
    "                visited.append(son)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        next_ = [[] for _ in range(n)]\n",
    "        pre_ = [[] for _ in range(n)]\n",
    "        ans, q = 0, [0]\n",
    "        visited = [False] * n\n",
    "        for u, v in connections:\n",
    "            next_[u].append(v)\n",
    "            pre_[v].append(u)\n",
    "        for u in q:\n",
    "            visited[u] = True\n",
    "            for v in next_[u]:\n",
    "                if not visited[v]:\n",
    "                    q.append(v)\n",
    "                    ans += 1\n",
    "            for v in pre_[u]:\n",
    "                if not visited[v]:\n",
    "                    q.append(v)\n",
    "        return ans\n",
    "\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        g=defaultdict(list)\n",
    "        for x,y in connections:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        visited=[0]*n\n",
    "        tem=1\n",
    "        queue=[0]\n",
    "        visited[0]=1\n",
    "        while queue:\n",
    "            m=len(queue)\n",
    "            tem+=1\n",
    "            for _ in range (0,m):\n",
    "                x=queue.pop(0)\n",
    "                for adj in g[x]:\n",
    "                    if visited[adj]==0:\n",
    "                        visited[adj]=tem\n",
    "                        queue.append(adj)\n",
    "        ans=0\n",
    "        print(visited)\n",
    "        for x,y in connections:\n",
    "            if visited[x]<visited[y]:\n",
    "                ans+=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        graph = []\n",
    "        for i in range(n):\n",
    "            graph.append([])\n",
    "        for u,v in connections:\n",
    "            graph[u].append((v,1))\n",
    "            graph[v].append((u,0))\n",
    "        #BFS starting\n",
    "        res = 0\n",
    "        queue = deque()\n",
    "        queue.append(0)\n",
    "        visited = [False] * n\n",
    "        visited[0] = True\n",
    "        while len(queue) > 0:\n",
    "            x = queue.popleft()\n",
    "            for y, w in graph[x]:\n",
    "                if visited[y]:\n",
    "                    continue\n",
    "                visited[y] = True\n",
    "                res += w\n",
    "                queue.append(y)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 将图视为无向图，从0开始bfs，遇到相连但是不在connections中的边就反向\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        hs = set((c[0], c[1]) for c in connections)\n",
    "        q = deque()\n",
    "        v = [[] for i in range(n)]\n",
    "        visit = [False] * n\n",
    "        res = 0\n",
    "\n",
    "        for c in connections:\n",
    "            v[c[0]].append(c[1])\n",
    "            v[c[1]].append(c[0])\n",
    "        \n",
    "        q.append(0)\n",
    "        while len(q) > 0:\n",
    "            p = q.popleft()\n",
    "            visit[p] = True\n",
    "\n",
    "            for nxt in v[p]:\n",
    "                if not visit[nxt]:\n",
    "                    if (nxt, p) not in hs:\n",
    "                        res += 1\n",
    "                        \n",
    "                    q.append(nxt)\n",
    "        \n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        edge = [[] for _ in range(n)]\n",
    "        for p, c in connections:\n",
    "            edge[p].append((c, 1))\n",
    "            edge[c].append((p, 0))\n",
    "        quee = [0]\n",
    "        vist = [False] * n\n",
    "        vist[0] = True\n",
    "        ans = 0\n",
    "        while quee:\n",
    "            i = quee.pop(0)\n",
    "            for n, c in edge[i]:\n",
    "                if not vist[n]:\n",
    "                    vist[n] = True\n",
    "                    ans += c\n",
    "                    quee.append(n)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        grapy = []\n",
    "        for i in range(n):\n",
    "            grapy.append([])\n",
    "        for u,v in connections:\n",
    "            grapy[v].append([u, 1])\n",
    "            grapy[u].append([v, 0])\n",
    "        ans = 0\n",
    "        visit = [0] * n\n",
    "        l = []\n",
    "        l.append(0)\n",
    "        visit[0] = 1\n",
    "        while len(l) > 0:\n",
    "            t = l.pop(0)\n",
    "            visit[t] = 1\n",
    "            for u,v in grapy[t]:\n",
    "                if visit[u] == 1:\n",
    "                    continue\n",
    "                ans = ans + v\n",
    "                l.append(u)\n",
    "        return n - 1 - ans\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for a, b in connections:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        \n",
    "        connections = set([(x, y) for x, y in connections])\n",
    "        ret = 0\n",
    "        visited = set()\n",
    "\n",
    "        # def dfs(i):\n",
    "        #     nonlocal ret\n",
    "        #     visited.add(i)\n",
    "        #     for j in graph[i]:\n",
    "        #         if j not in visited:\n",
    "        #             if (i, j) in connections: ret += 1\n",
    "        #             dfs(j)\n",
    "        # dfs(0)\n",
    "\n",
    "        queue = [0]\n",
    "        while queue:\n",
    "            i = queue.pop(0)\n",
    "            visited.add(i)\n",
    "            for j in graph[i]:\n",
    "                if j not in visited:\n",
    "                    if (i, j) in connections: ret += 1\n",
    "                    queue.append(j)\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        edges = [[] for _ in range(n)]\n",
    "        for edge in connections:\n",
    "            edges[edge[0]].append((1,edge[1]))\n",
    "            edges[edge[1]].append((0,edge[0]))\n",
    "        def bfs():\n",
    "            res = 0\n",
    "            Q = deque([0])\n",
    "            visited = {0}\n",
    "            while Q:\n",
    "                cur_node = Q.pop()\n",
    "                for num, child in edges[cur_node]:\n",
    "                    if child not in visited:\n",
    "                        res += num\n",
    "                        visited.add(child)\n",
    "                        Q.appendleft(child)\n",
    "            return res\n",
    "        return bfs()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        visited = set([0])\n",
    "        ret = 0\n",
    "        for _ in range(n):\n",
    "            for x, y in connections:\n",
    "                if x in visited and y not in visited:\n",
    "                    ret += 1\n",
    "                    visited.add(y)\n",
    "                elif y in visited and x not in visited:\n",
    "                    visited.add(x)\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in connections:\n",
    "            g[x].append((y, 1))\n",
    "            g[y].append((x, 0))\n",
    "        visited = set([0])\n",
    "        q = deque([0])\n",
    "        ret = 0\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            for y, c in g[x]:\n",
    "                if y not in visited:\n",
    "                    visited.add(y)\n",
    "                    ret += c\n",
    "                    q.append(y)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        lookup = {}\n",
    "        for i in range(n-1):\n",
    "            lookup[connections[i][1]] = lookup.get(connections[i][1], []) + [(connections[i][0], 0)]\n",
    "            lookup[connections[i][0]] = lookup.get(connections[i][0], []) + [(connections[i][1], 1)]\n",
    "        queue = collections.deque()\n",
    "        queue.append(0)\n",
    "        visited = [0 for _ in range(n)]\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for i in range(size):\n",
    "                cur_num = queue.popleft()\n",
    "                for num in lookup[cur_num]:\n",
    "                    if num[1] == 1 and not visited[num[0]]:\n",
    "                        res += 1\n",
    "                    if not visited[num[0]]:\n",
    "                        queue.append(num[0])\n",
    "                visited[cur_num] = 1\n",
    "        return res\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        visited = set()\n",
    "        visited.add(0)\n",
    "        result = 0\n",
    "        tmp_conn = []\n",
    "        for i in range(n):\n",
    "            tmp_conn.append([])\n",
    "        search_list = [0]\n",
    "        for a, b in connections:\n",
    "            tmp_conn[a].append([b, 1])\n",
    "            tmp_conn[b].append([a, 0])\n",
    "        while search_list:\n",
    "            tmp_city = search_list.pop(0)\n",
    "            for b, need_chg in tmp_conn[tmp_city]:\n",
    "                if b not in visited:\n",
    "                    visited.add(b)\n",
    "                    search_list.append(b)\n",
    "                    result += need_chg\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        visited = set()\n",
    "        visited.add(0)\n",
    "        result = 0\n",
    "        tmp_conn = []\n",
    "        for i in range(n):\n",
    "            tmp_conn.append([])\n",
    "        search_list = [0]\n",
    "        for a, b in connections:\n",
    "            tmp_conn[a].append([b, 1])\n",
    "            tmp_conn[b].append([a, 0])\n",
    "        while search_list:\n",
    "            tmp_city = search_list.pop(0)\n",
    "            for b, need_chg in tmp_conn[tmp_city]:\n",
    "                if b not in visited:\n",
    "                    visited.add(b)\n",
    "                    search_list.append(b)\n",
    "                    result += need_chg\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#BFS\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        roads = []\n",
    "        for c in connections:\n",
    "            roads.append((c[0],c[1]))\n",
    "        roads = set(roads)\n",
    "\n",
    "        mp = defaultdict(list)\n",
    "        for c in connections:\n",
    "            mp[c[0]].append(c[1])\n",
    "            mp[c[1]].append(c[0])\n",
    "\n",
    "        queue = [0]\n",
    "        seen = set()\n",
    "        seen.add(0)\n",
    "        ans = 0\n",
    "        print(mp)\n",
    "        while queue:\n",
    "            length = len(queue)\n",
    "            for _ in range(length):\n",
    "                cur = queue.pop(0)\n",
    "                for n in mp[cur]:\n",
    "                    if n not in seen and (cur,n) in roads:\n",
    "                        ans += 1\n",
    "                    if n not in seen:\n",
    "                        seen.add(n)\n",
    "                        queue.append(n)\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        q= deque()\n",
    "        q.append(0)\n",
    "\n",
    "        recorder = defaultdict(list)\n",
    "        for x, y in connections:\n",
    "            recorder[x].append((y, 1))\n",
    "            recorder[y].append((x, 0))\n",
    "\n",
    "        ans = 0\n",
    "        visited = set()\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            visited.add(node)\n",
    "            for next_city, weight in recorder[node]:\n",
    "                if next_city not in visited:\n",
    "                    q.append(next_city)\n",
    "                    ans += weight\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        q= deque()\n",
    "        q.append(0)\n",
    "\n",
    "        recorder = defaultdict(list)\n",
    "        for x, y in connections:\n",
    "            recorder[x].append((y, 1))\n",
    "            recorder[y].append((x, 0))\n",
    "\n",
    "        ans = 0\n",
    "        visited = set()\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            visited.add(node)\n",
    "            for next_city, weight in recorder[node]:\n",
    "                if next_city not in visited:\n",
    "                    q.append(next_city)\n",
    "                    ans += weight\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        #bfs\n",
    "        dict = defaultdict(list)\n",
    "        dict2 = defaultdict(list)       \n",
    "        for c in connections:\n",
    "            dict[c[0]].append(c[1])\n",
    "            dict2[c[0]].append(c[1])\n",
    "            dict[c[1]].append(c[0])\n",
    "        cnt = 0 \n",
    "        q = deque()\n",
    "        q.append(0)\n",
    "        visited = set()\n",
    "        visited.add(0)\n",
    "        while q:\n",
    "            item = q.popleft()\n",
    "            for i in dict[item]:\n",
    "                if i in visited:\n",
    "                    continue\n",
    "                if i in dict2[item]:\n",
    "                    cnt += 1\n",
    "                q.append(i)\n",
    "                visited.add(i)\n",
    "        return cnt\n",
    "        #proof： 可以从0向所有点bfs的理由是，这是一颗树（树的定义比有向无环图更严格，此题若是仅定义为有向无环图则解法是错误），如此走到一个点的路径是其走向0的必然且唯一路径\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        #bfs\n",
    "        dict = defaultdict(list)\n",
    "        dict2 = defaultdict(list)       \n",
    "        for c in connections:\n",
    "            dict[c[0]].append(c[1])\n",
    "            dict2[c[0]].append(c[1])\n",
    "            dict[c[1]].append(c[0])\n",
    "        cnt = 0 \n",
    "        q = deque()\n",
    "        q.append(0)\n",
    "        visited = set()\n",
    "        visited.add(0)\n",
    "        while q:\n",
    "            item = q.popleft()\n",
    "            for i in dict[item]:\n",
    "                if i in visited:\n",
    "                    continue\n",
    "                if i in dict2[item]:\n",
    "                    cnt += 1\n",
    "                q.append(i)\n",
    "                visited.add(i)\n",
    "        return cnt\n",
    "        #proof： 可以从0向所有点bfs的理由是，这是一颗树，如此走到一个点的路径是其走向0的必然且唯一路径\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "\n",
    "        visited = set()\n",
    "        linked_dict = dict()\n",
    "\n",
    "        ans = 0\n",
    "        find_flag = 1\n",
    "\n",
    "        for index in range(len(connections)):\n",
    "            if connections[index][0] in linked_dict:\n",
    "\n",
    "                linked_dict[connections[index][0]].append([connections[index][1], 0])\n",
    "            \n",
    "            else:\n",
    "                linked_dict[connections[index][0]] = []\n",
    "                linked_dict[connections[index][0]].append([connections[index][1], 0])\n",
    "        \n",
    "            if connections[index][1] in linked_dict:\n",
    "                linked_dict[connections[index][1]].append([connections[index][0], 1])\n",
    "            \n",
    "            else:\n",
    "                linked_dict[connections[index][1]] = []\n",
    "                linked_dict[connections[index][1]].append([connections[index][0], 1])\n",
    "\n",
    "\n",
    "        bfs = deque()\n",
    "        bfs.append(0)\n",
    "        \n",
    "        while(len(bfs) != 0):\n",
    "            cur_city = bfs.popleft()\n",
    "            visited.add(cur_city)\n",
    "            for item in linked_dict[cur_city]:\n",
    "                next_city, dire = item\n",
    "                if next_city not in visited:\n",
    "                    if dire == 0:\n",
    "                        ans += 1\n",
    "                    bfs.append(next_city)\n",
    "            \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        #1 把有向图变为无向图\n",
    "        connection_dict = {}\n",
    "        for connection in connections:\n",
    "            city1, city2 = connection\n",
    "            if not city1 in connection_dict:\n",
    "                connection_dict[city1] = []\n",
    "            if not city2 in connection_dict:\n",
    "                connection_dict[city2] = []\n",
    "            connection_dict[city1].append([city2, False])  # 需要记录原来有向图的方向，后面会用到\n",
    "            connection_dict[city2].append([city1, True])\n",
    "\n",
    "        #2 遍历无向图\n",
    "        revise_count = 0 # 记录修改次数\n",
    "        stack = [0] # 使用栈来模拟DFS\n",
    "        visited_cities = {}  # 已遍历过的城市\n",
    "        while len(stack) > 0:\n",
    "            city = stack.pop() \n",
    "            visited_cities[city] = 1\n",
    "            for connected_city, direction in connection_dict[city]:\n",
    "                if not connected_city in visited_cities:\n",
    "                    stack.append(connected_city)\n",
    "                    if direction is False:\n",
    "                        revise_count += 1\n",
    "        \n",
    "        return revise_count\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        nodes = {}\n",
    "        nodes_parent = {}\n",
    "        nodes_direct = {}\n",
    "        \n",
    "        for i in range(n):\n",
    "            nodes[i] = []\n",
    "            nodes_parent[i] = None\n",
    "            nodes_direct[i] = []\n",
    "        \n",
    "        for conn in connections:\n",
    "            nodes[conn[0]].append(conn[1])\n",
    "            nodes[conn[1]].append(conn[0])\n",
    "            nodes_direct[conn[0]].append(conn[1])\n",
    "        \n",
    "        q = [0]\n",
    "        flag = [0 for i in range(n)]\n",
    "        flag_0 = [1] + [0 for i in range(n-1)]\n",
    "        ans = 0\n",
    "        while len(q) > 0:\n",
    "            n = q.pop(0)\n",
    "            if n != 0:\n",
    "                p = nodes_parent[n]\n",
    "                if p not in nodes_direct[n] or n not in nodes_direct.keys():\n",
    "                    ans += 1\n",
    "                    nodes_direct[n] = p\n",
    "            \n",
    "            childs = nodes[n]\n",
    "            for c in childs:\n",
    "                if not flag[c]:\n",
    "                    q.append(c)\n",
    "                    nodes_parent[c] = n           \n",
    "            flag[n] = 1\n",
    "            \n",
    "        return ans   \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        con =dict()\n",
    "        for r in connections:\n",
    "            if r[0] in con:\n",
    "                con[r[0]].append([r[1],-1])\n",
    "            else:\n",
    "                con[r[0]] =[[r[1],-1]]\n",
    "            if r[1] in con:\n",
    "                con[r[1]].append([r[0],1])\n",
    "            else:\n",
    "                con[r[1]] =[[r[0],1]]\n",
    "        ans =0\n",
    "        q=deque()\n",
    "        q.append(0)\n",
    "        visited =set()\n",
    "        visited.add(0)\n",
    "        while q:\n",
    "            tmp = q.popleft()\n",
    "            for t in con[tmp]:\n",
    "                if t[0] not in visited:\n",
    "                    visited.add(t[0])\n",
    "                    q.append(t[0])\n",
    "                    if t[1] ==-1:\n",
    "                        ans +=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "\n",
    "        valid=set()\n",
    "        valid.add(0)\n",
    "        res=0\n",
    "        ind={i:[] for i in range(n)}\n",
    "        outd={i:[] for i in range(n)}\n",
    "\n",
    "        stack=[0]\n",
    "        for s,e in connections:\n",
    "            ind[e].append(s)\n",
    "            outd[s].append(e)\n",
    "\n",
    "        while stack:\n",
    "            cur=stack.pop(0)\n",
    "            for rnex in ind[cur]:\n",
    "                if rnex not in valid:\n",
    "                    valid.add(rnex)\n",
    "                    stack.append(rnex)\n",
    "            for nex in outd[cur]: \n",
    "                if nex not in valid:\n",
    "                    valid.add(nex)\n",
    "                    stack.append(nex)\n",
    "                    res=res+1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "\n",
    "        father_nodes = {}\n",
    "        child_nodes = {}\n",
    "\n",
    "        # get each node's father and children\n",
    "        for pair in connections:\n",
    "            father, child = pair[0], pair[1]\n",
    "            if(father not in child_nodes):\n",
    "                child_nodes[father] = set([child])\n",
    "            else:\n",
    "                child_nodes[father].add(child)\n",
    "            if(child not in father_nodes):\n",
    "                father_nodes[child] = set([father])\n",
    "            else:\n",
    "                father_nodes[child].add(father)            \n",
    "        \n",
    "        # memory the cities that can reach at zero\n",
    "        good_cities = set([0])\n",
    "        change_cnt = 0\n",
    "\n",
    "        for pair in connections:\n",
    "            father, child = pair[0],pair[1]\n",
    "\n",
    "            # can't do anything\n",
    "            if(father not in good_cities and child not in good_cities):\n",
    "                continue\n",
    "            #  at least one node is good\n",
    "            if(father in good_cities and child not in good_cities):\n",
    "                change_cnt += 1\n",
    "                good_cities.add(child)\n",
    "            elif(father not in good_cities and child in good_cities):\n",
    "                good_cities.add(father)\n",
    "            #  then both nodes can reach at zero\n",
    "            \n",
    "            # father cities\n",
    "            fathers,children = [],[]\n",
    "            fathers += [item for item in father_nodes[father] if item not in good_cities] if father in father_nodes else []\n",
    "            fathers += [item for item in father_nodes[child] if item not in good_cities] if child in father_nodes else []\n",
    "            # children cities\n",
    "            children += [item for item in child_nodes[father] if item not in good_cities] if father in child_nodes else []\n",
    "            children += [item for item in child_nodes[child] if item not in good_cities] if child in child_nodes else []\n",
    "            \n",
    "            while(fathers or children):\n",
    "                if(fathers):\n",
    "                    tmp_city = fathers.pop()\n",
    "                else:\n",
    "                    tmp_city = children.pop()\n",
    "                    change_cnt += 1\n",
    "                good_cities.add(tmp_city)\n",
    "                fathers += [item for item in father_nodes[tmp_city] if item not in good_cities] if tmp_city in father_nodes else []\n",
    "                children += [item for item in child_nodes[tmp_city] if item not in good_cities] if tmp_city in child_nodes else []\n",
    "            \n",
    "        return change_cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        link = [set() for i in range(n)]\n",
    "        re = [set() for i in range(n)]\n",
    "        \n",
    "        for a,b in connections:\n",
    "            link[a].add(b)\n",
    "            re[b].add(a)\n",
    "\n",
    "        queue = [0]\n",
    "        res = 0\n",
    "        touched = set()\n",
    "        while len(queue) > 0:\n",
    "            cur = queue[0]\n",
    "            queue = queue[1:]\n",
    "            for k in link[cur]:\n",
    "                res += 1\n",
    "                queue.append(k)\n",
    "                re[k].remove(cur)\n",
    "            for k in re[cur]:\n",
    "                queue.append(k)\n",
    "                link[k].remove(cur)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        graph = {i:[] for i in range(n)}\n",
    "        conn = set()\n",
    "        for (u, v) in connections:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "            conn.add((u, v))\n",
    "        \n",
    "        visited = [False] * n\n",
    "        queue = deque([0])\n",
    "\n",
    "        routes = set()\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            visited[node] = True\n",
    "            for neighbor in graph[node]:\n",
    "                if visited[neighbor] == False:\n",
    "                    queue.append(neighbor)\n",
    "                    routes.add((neighbor, node))\n",
    "        \n",
    "        return len(conn - routes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: list) -> int:\n",
    "        To,In = [set() for i in range(n)],[set() for i in range(n)]\n",
    "        '''\n",
    "        To[x] -> y\n",
    "        In[y] <- x\n",
    "        '''\n",
    "        for x,y in connections:\n",
    "            To[x].add(y)\n",
    "            In[y].add(x)\n",
    "\n",
    "        q,cnt = Queue(),0\n",
    "        q.put(0)\n",
    "        while not q.empty():\n",
    "            root = q.get()\n",
    "            '''\n",
    "            子节点 -> root，子节点入队。然后继续遍历子节点。\n",
    "            \n",
    "            同时删除 子节点 -> root 这条路线，因为访问子节点可到达的路径时，可能会回到当前节点。\n",
    "            '''\n",
    "            for son in In[root]:\n",
    "                To[son].discard(root)\n",
    "                q.put(son)\n",
    "\n",
    "            '''\n",
    "            root -> 子节点，子节点入队。\n",
    "                我们必须让在 root 下面的子节点入队。之前我们已经删除了 root -> 父亲节点 这条路径(不管存不存在)。\n",
    "            '''\n",
    "            cnt += len(To[root])\n",
    "            for son in To[root]:\n",
    "                q.put(son)\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, cs: List[List[int]]) -> int:\n",
    "        e = defaultdict(set)\n",
    "        for u,v in cs:\n",
    "            e[u].add((v,0))\n",
    "            e[v].add((u,1))\n",
    "        ans = 0\n",
    "        q = deque([0])\n",
    "        vis = {0}\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            for nxt,tag in e[cur]:\n",
    "                if nxt in vis:\n",
    "                    continue\n",
    "                if tag == 0:\n",
    "                    ans += 1\n",
    "                vis.add(nxt)\n",
    "                q.append(nxt)\n",
    "                    \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        edges={}\n",
    "        for i in range(n):\n",
    "            edges[i]=set()\n",
    "        for i in connections:\n",
    "            a,b=i[0],i[1]\n",
    "            edges[a].add(b)\n",
    "            edges[b].add(a)\n",
    "        queue=[0]\n",
    "        covered={0}\n",
    "        layer={}\n",
    "        layer[0]=0\n",
    "        cnt=1\n",
    "        while queue:\n",
    "            tmp=[]\n",
    "            for node in queue:\n",
    "                for neighbor in edges[node]:\n",
    "                    if neighbor not in covered:\n",
    "                        covered.add(neighbor)\n",
    "                        tmp.append(neighbor)\n",
    "                        layer[neighbor]=cnt\n",
    "            queue=tmp\n",
    "            cnt+=1\n",
    "        ans=0\n",
    "        for i in connections:\n",
    "            a,b=i[0],i[1]\n",
    "            if layer[a]<layer[b]:\n",
    "                ans+=1\n",
    "        return ans\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        graph = {i:set() for i in range(n)}\n",
    "\n",
    "        for start, end in connections:\n",
    "            graph[start].add((end, 1))\n",
    "            graph[end].add((start, 0))\n",
    "        \n",
    "        result = 0\n",
    "        visited = set()\n",
    "        queue = deque()\n",
    "        \n",
    "        queue.append(0)\n",
    "        visited.add(0)\n",
    "\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            for neighbor, cost in graph[node]:\n",
    "                if neighbor in visited:\n",
    "                    continue\n",
    "                result += cost\n",
    "                queue.append(neighbor)\n",
    "                visited.add(neighbor)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        edge = defaultdict(lambda: defaultdict(list))\n",
    "        for a, b in connections:\n",
    "            edge[a]['to'].append(b)\n",
    "            edge[b]['from'].append(a)\n",
    "        \n",
    "        ans = 0\n",
    "        stack = [0]\n",
    "        visit = [1] + [0]*(n-1)  # 记录节点的访问状态\n",
    "        while stack:\n",
    "            nxt = []\n",
    "            for node in stack:\n",
    "                for b in edge[node]['to']:\n",
    "                    if not visit[b]:\n",
    "                        ans += 1\n",
    "                        nxt.append(b)\n",
    "                        visit[b] = 1\n",
    "                for a in edge[node]['from']:\n",
    "                    if not visit[a]:\n",
    "                        nxt.append(a)\n",
    "                        visit[a] = 1\n",
    "            stack = nxt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        edge = defaultdict(lambda: defaultdict(list))\n",
    "        for a, b in connections:\n",
    "            edge[a]['to'].append(b)\n",
    "            edge[b]['from'].append(a)\n",
    "        \n",
    "        ans = 0\n",
    "        visited = [False] * n\n",
    "        stack = [0]\n",
    "        visited[0] = True\n",
    "\n",
    "        while stack:\n",
    "            num = len(stack)\n",
    "            for _ in range(num):\n",
    "                node = stack.pop(0)\n",
    "                for b in edge[node]['to']:\n",
    "                    if not visited[b]:\n",
    "                        ans += 1\n",
    "                        visited[b] = True\n",
    "                        stack.append(b)\n",
    "                for a in edge[node]['from']:\n",
    "                    if not visited[a]:\n",
    "                        visited[a] = True\n",
    "                        stack.append(a)\n",
    "        return ans\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def add(self, conn, a,b):\n",
    "        aset=conn.get(a,set())\n",
    "        aset.add(b)\n",
    "        conn[a]=aset\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        uniconn={}\n",
    "        biconn={}\n",
    "        for a,b in connections:\n",
    "            self.add(uniconn,a,b)\n",
    "            self.add(biconn,a,b)\n",
    "            self.add(biconn,b,a)\n",
    "\n",
    "        queue=[0]\n",
    "        visited=set()\n",
    "        res=0\n",
    "        while len(queue)>0:\n",
    "            a=queue[0]\n",
    "            queue=queue[1:]\n",
    "            visited.add(a)\n",
    "            for b in biconn.get(a):\n",
    "                if b not in visited:\n",
    "                    queue.append(b)\n",
    "                    if a not in uniconn.get(b,set()):\n",
    "                        res+=1\n",
    "\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        status = {}\n",
    "        for x,y in connections:\n",
    "            if x not in status: status[x] = {'from':[],'to':[]}\n",
    "            if y not in status: status[y] = {'from':[],'to':[]}\n",
    "            status[x]['to'].append(y)\n",
    "            status[y]['from'].append(x)\n",
    "\n",
    "        visited = set()\n",
    "        citys = deque()\n",
    "        citys.append(0)\n",
    "        res = 0\n",
    "\n",
    "        while citys:\n",
    "            city = citys.popleft()\n",
    "            visited.add(city)\n",
    "            for y in status[city]['to']:\n",
    "                if y not in visited:\n",
    "                    res+=1\n",
    "                    citys.append(y)\n",
    "                    visited.add(y)\n",
    "            for y in status[city]['from']:\n",
    "                if y not in visited:\n",
    "                    citys.append(y)\n",
    "                    visited.add(y)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        #从0开始逆向bfs，对于该节点的去路要做修改，对于来向道路则不变\n",
    "        # edges=defaultdict(list)\n",
    "        edges=defaultdict(lambda :defaultdict(list))\n",
    "        for i,j in connections:\n",
    "            edges[i]['to'].append(j)#i->j\n",
    "            edges[j]['from'].append(i)#i->j\n",
    "        ans=0\n",
    "        que=[0]#从起点开始逆向搜索\n",
    "        vis={0}#起点加入\n",
    "        while que:\n",
    "            for i in range(len(que)):\n",
    "                node=que.pop(0)\n",
    "                for j in edges[node]['to']:#node->j\n",
    "                    if j not in vis:\n",
    "                        ans+=1\n",
    "                        que.append(j)\n",
    "                        vis.add(j)\n",
    "                for i in edges[node]['from']:#i->node\n",
    "                    if i not in vis:\n",
    "                        que.append(i)\n",
    "                        vis.add(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        info = {i:{\"to\":[], \"from\":[]} for i in range(n)}\n",
    "        for f, t in connections:\n",
    "            info[f][\"to\"].append(t)\n",
    "            info[t][\"from\"].append(f)\n",
    "        tmp = [0]\n",
    "        seen = {0}\n",
    "        res = 0\n",
    "        while tmp:\n",
    "            vertex = tmp.pop()\n",
    "            for node in info[vertex][\"to\"]:\n",
    "                if node not in seen:\n",
    "                    tmp.append(node)\n",
    "                    res += 1\n",
    "                    seen.add(node)\n",
    "            for node in info[vertex][\"from\"]:\n",
    "                if node not in seen:\n",
    "                    tmp.append(node)\n",
    "                    seen.add(node)                    \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        info = {i:{\"to\":[], \"from\":[]} for i in range(n)}\n",
    "        for f, t in connections:\n",
    "            info[f][\"to\"].append(t)\n",
    "            info[t][\"from\"].append(f)\n",
    "        tmp = [0]\n",
    "        seen = {0}\n",
    "        res = 0\n",
    "        while tmp:\n",
    "            vertex = tmp.pop()\n",
    "            for node in info[vertex][\"to\"]:\n",
    "                if node not in seen:\n",
    "                    tmp.append(node)\n",
    "                    res += 1\n",
    "                    seen.add(node)\n",
    "            for node in info[vertex][\"from\"]:\n",
    "                if node not in seen:\n",
    "                    tmp.append(node)\n",
    "                    seen.add(node)                    \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict \n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        g = defaultdict(set)\n",
    "        gr = defaultdict(set)\n",
    "        for [a, b] in connections:\n",
    "            g[a].add(b)\n",
    "            gr[b].add(a)\n",
    "        \n",
    "        g[0].add(0)\n",
    "        Q = [(0,0)]\n",
    "        ans = 0\n",
    "        while Q:\n",
    "            u, pre = Q.pop(0)\n",
    "            if pre not in g[u]:\n",
    "                ans += 1\n",
    "            for v in g[u]:\n",
    "                if v != pre:\n",
    "                    Q.append((v, u))\n",
    "            for v in gr[u]:\n",
    "                if v != pre:\n",
    "                    Q.append((v, u))\n",
    "        \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        child = defaultdict(set)\n",
    "        re = defaultdict(set)\n",
    "\n",
    "        for x, y in connections:\n",
    "            child[x].add(y)\n",
    "            re[y].add(x)\n",
    "        \n",
    "        q = deque()\n",
    "        q.append(0)\n",
    "        seen = set()\n",
    "        seen.add(0)\n",
    "        \n",
    "        ans = 0\n",
    "\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "\n",
    "            for ch in re[node]:\n",
    "                if ch not in seen:\n",
    "                    q.append(ch)\n",
    "                    seen.add(ch)\n",
    "            \n",
    "            for ch in child[node]:\n",
    "                if ch not in seen:\n",
    "                    q.append(ch)\n",
    "                    ans += 1\n",
    "                    seen.add(ch)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        '''实际就是个二叉树，对于线路。 那么可以用二叉树的方式，二叉树bfs是如何遍历的 添加root节点，左右节点不为空那么就加入节点， 那么同理可以利用这个特性，先构造左右节点 获取每个的进度和出度\n",
    "\n",
    "用队列遍历，对于出度的节点，说明不是指向我们，那么数量需要加上一个， 而对于进度节点说明指向是正确，那么无需改变。 遍历完毕后，就是实际答案'''\n",
    "\n",
    "        outDegrees=collections.defaultdict(set)\n",
    "        inDegrees=collections.defaultdict(set)\n",
    "        for x,y in connections:\n",
    "            outDegrees[x].add(y)\n",
    "            inDegrees[y].add(x)\n",
    "        # print(outDegrees)  \n",
    "        # print(inDegrees)  \n",
    "        q=deque()\n",
    "        q.append(0)\n",
    "        cnt=set()\n",
    "        ans=0\n",
    "        while q:\n",
    "            idx= q.pop()\n",
    "     \n",
    "            cnt.add(idx)\n",
    "            for i in outDegrees[idx]:\n",
    "                if i in cnt:\n",
    "                    continue\n",
    "                ans+=1\n",
    "                q.appendleft(i)\n",
    "            for i in inDegrees[idx]:\n",
    "                if i in cnt:\n",
    "                    continue\n",
    "                q.appendleft(i)    \n",
    "        return ans    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        a2b, b2a = collections.defaultdict(set), collections.defaultdict(set)\n",
    "        for i, j in connections:\n",
    "            a2b[i].add(j)\n",
    "            b2a[j].add(i)\n",
    "        s = [0]\n",
    "        seen = set(s)\n",
    "        cnt = 0\n",
    "        while s:\n",
    "            city = s.pop()\n",
    "            for nxt in b2a[city] | a2b[city]:\n",
    "                if nxt not in seen:\n",
    "                    cnt += nxt in a2b[city]\n",
    "                    seen.add(nxt)\n",
    "                    s.append(nxt)\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        forward, backward = defaultdict(set), defaultdict(set)\n",
    "        for connection in connections:\n",
    "            forward[connection[0]].add(connection[1])\n",
    "            backward[connection[1]].add(connection[0])\n",
    "        open_set = [0]\n",
    "        visited = set([0])\n",
    "        ans = 0\n",
    "        while open_set:\n",
    "            cur_city = open_set.pop(0)\n",
    "            for back_neighbor in backward[cur_city]:\n",
    "                if back_neighbor not in visited:\n",
    "                    open_set.append(back_neighbor)\n",
    "                    visited.add(back_neighbor)\n",
    "            for forward_neighbor in forward[cur_city]:\n",
    "                if forward_neighbor not in visited:\n",
    "                    open_set.append(forward_neighbor)\n",
    "                    visited.add(forward_neighbor)\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        a2b, b2a = collections.defaultdict(set), collections.defaultdict(set)\n",
    "        for i, j in connections:\n",
    "            a2b[i].add(j)\n",
    "            b2a[j].add(i)\n",
    "        s = [0]\n",
    "        seen = set(s)\n",
    "        cnt = 0\n",
    "        while s:\n",
    "            city = s.pop()\n",
    "            for nxt in b2a[city] | a2b[city]:\n",
    "                if nxt not in seen:\n",
    "                    cnt += nxt in a2b[city]\n",
    "                    seen.add(nxt)\n",
    "                    s.append(nxt)\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        graph = {i: set() for i in range(n)}\n",
    "        graph2 = {i: set() for i in range(n)}\n",
    "        for u, v in connections:\n",
    "            graph[u].add(v)\n",
    "            graph2[v].add(u)\n",
    "        visited = [False] * n\n",
    "        visited[0] = True\n",
    "        start = [0]\n",
    "        ans = 0\n",
    "        while start:\n",
    "            u = start.pop(0)\n",
    "            for v in graph[u]:\n",
    "                if not visited[v]:\n",
    "                    visited[v] = True\n",
    "                    start.append(v)\n",
    "                    ans += 1\n",
    "            for v in graph2[u]:\n",
    "                if not visited[v]:\n",
    "                    visited[v] = True\n",
    "                    start.append(v)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict \n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        edges = defaultdict(set)\n",
    "        r_edges = defaultdict(set)\n",
    "        for [x, y] in connections:\n",
    "            edges[x].add(y)\n",
    "            r_edges[y].add(x)\n",
    "\n",
    "        edges[0].add(0)\n",
    "        ans = 0\n",
    "        def dfs(x, pre):\n",
    "            nonlocal ans \n",
    "            if not pre in edges[x]:\n",
    "                ans += 1\n",
    "            for y in edges[x]:\n",
    "                if y != pre:\n",
    "                    dfs(y, x)\n",
    "            for y in r_edges[x]:\n",
    "                if y != pre:\n",
    "                    dfs(y, x)\n",
    "        \n",
    "        Q = [(0, 0)]\n",
    "        while Q:\n",
    "            u, pre = Q.pop(0)\n",
    "            for v in edges[u]:\n",
    "                if v != pre:\n",
    "                    Q.append((v, u))\n",
    "                    if u not in edges[v]:\n",
    "                        ans += 1\n",
    "            for v in r_edges[u]:\n",
    "                if v != pre:\n",
    "                    Q.append((v, u))\n",
    "\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        children = [[] for _ in range(n)]\n",
    "        mark = [0] * n\n",
    "\n",
    "        for i in range(len(connections)):\n",
    "            children[connections[i][0]].append(-connections[i][1])\n",
    "            children[connections[i][1]].append(connections[i][0])\n",
    "        \n",
    "        ans = 0\n",
    "        def dfs(p):\n",
    "            #print(p)\n",
    "            nonlocal ans\n",
    "            for e in children[p]:\n",
    "                if e < 0 and mark[abs(e)] == 0:\n",
    "                    ans += 1\n",
    "                    mark[abs(e)] = 1\n",
    "                    dfs(abs(e))\n",
    "                elif e > 0:\n",
    "                    mark[e] = 1\n",
    "                    dfs(e)\n",
    "        \n",
    "        mark[0] = 1\n",
    "        dfs(0)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        zheng = [[] for _ in range(n)]\n",
    "        fan = [[] for _ in range(n)]\n",
    "        res = 0\n",
    "        for i,j in connections:\n",
    "            zheng[i].append(j)\n",
    "            fan[j].append(i)\n",
    "        def gen(x,fa):\n",
    "            nonlocal res\n",
    "            for i in zheng[x]:\n",
    "                if i!=fa:\n",
    "                    res+=1\n",
    "                    gen(i,x)\n",
    "            for i in fan[x]:\n",
    "                if i!=fa:\n",
    "                    gen(i,x)\n",
    "        gen(0,-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        graph, queue, result, visited = defaultdict(deque), deque([0]), 0, [True] + [False] * (n - 1)\n",
    "        for u, v in connections:\n",
    "            graph[u].append((v, 1))\n",
    "            graph[v].append((u, 0))\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for v, cost in graph[cur]:\n",
    "                if not visited[v]:\n",
    "                    visited[v] = True\n",
    "                    result += cost\n",
    "                    queue.append(v)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        graph, queue, result, visited = defaultdict(deque), deque([0]), 0, [True] + [False] * (n - 1)\n",
    "        for u, v in connections:\n",
    "            graph[u].append((v, 1))\n",
    "            graph[v].append((u, 0))\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for v, cost in graph[cur]:\n",
    "                if not visited[v]:\n",
    "                    visited[v] = True\n",
    "                    result += cost\n",
    "                    queue.append(v)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        ways_node = [[] for _ in range(n)]\n",
    "        for way in connections:\n",
    "            ways_node[way[0]].append(way)\n",
    "            ways_node[way[1]].append(way)\n",
    "        self.total_num = 0\n",
    "        self.visit_list = [0 for _ in range(n)]\n",
    "        def dfs(node):\n",
    "            for way in ways_node[node]:\n",
    "                next_node_index = 0 if way[1]==node else 1\n",
    "                next_node = way[next_node_index]\n",
    "                if self.visit_list[next_node]==0:\n",
    "                    if next_node_index==1:\n",
    "                        self.total_num += 1\n",
    "                    self.visit_list[next_node] = 1\n",
    "                    dfs(next_node)\n",
    "        self.visit_list[0] = 1\n",
    "        dfs(0)\n",
    "        return self.total_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        vis = [False] * n\n",
    "        # conn = [[]] * n\n",
    "        conn = []\n",
    "        for i in range(n):\n",
    "            conn.append([])\n",
    "        for elem in connections:\n",
    "            conn[elem[0]].append(elem)\n",
    "            conn[elem[1]].append(elem)\n",
    "        res = 0\n",
    "        def dfs(node):\n",
    "            vis[node] = True\n",
    "            for elem in conn[node]:\n",
    "                if elem[0] == node and vis[elem[1]] == False:\n",
    "                    nonlocal res\n",
    "                    res += 1\n",
    "                    dfs(elem[1])\n",
    "                if elem[1] == node and vis[elem[0]] == False:\n",
    "                    dfs(elem[0])\n",
    "        dfs(0)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.count = 0\n",
    "\n",
    "    def bfs( self,nodeDict,node,edgeP):\n",
    "        for edge in nodeDict[node]:\n",
    "            if edge == edgeP:\n",
    "                continue\n",
    "\n",
    "            tmpNode = edge[0]\n",
    "            if edge[1] != node:\n",
    "                self.count += 1\n",
    "                tmpNode = edge[1]\n",
    "            self.bfs(nodeDict,tmpNode,edge)\n",
    "\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        nodeDict = {}\n",
    "        for i in range(n):\n",
    "            nodeDict[i]=[]\n",
    "        for edge in connections:\n",
    "            for i in edge:\n",
    "                nodeDict[i].append(edge)\n",
    "\n",
    "        self.bfs(nodeDict,0,None)\n",
    "\n",
    "        return self.count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        count = 0\n",
    "        visited = [False] * n\n",
    "        def build_graph(n, connections):\n",
    "            graph = [[] for _ in range(n)]\n",
    "            for i in connections:\n",
    "                graph[i[0]].append(i[1])\n",
    "                graph[i[1]].append(-i[0])\n",
    "            return graph\n",
    "        \n",
    "        def dfs(graph, city):\n",
    "            visited[city] = True\n",
    "            for i in graph[city]:\n",
    "                if not visited[abs(i)]:\n",
    "                    if i > 0:\n",
    "                        nonlocal count\n",
    "                        count += 1\n",
    "                    dfs(graph, abs(i))\n",
    "        \n",
    "        graph = build_graph(n, connections)\n",
    "        # print(graph)\n",
    "        dfs(graph, 0)\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def buildGraph(self, n, connections) -> List[List[int]]:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for u,v in connections:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(-u)\n",
    "        return graph\n",
    "\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        g = self.buildGraph(n, connections)\n",
    "        v = [0 for _ in range(n)]\n",
    "        def dfs(g, v, i):\n",
    "            v[i] = 1\n",
    "            res = 0\n",
    "            for to in g[i]:\n",
    "                if v[abs(to)]==1:\n",
    "                    continue\n",
    "                if to>0:\n",
    "                    res +=1 \n",
    "                res += dfs(g,v,abs(to))\n",
    "            return res\n",
    "        return dfs(g,v,0)\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        graph = []\n",
    "        self.res = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            graph.append([])\n",
    "        \n",
    "        for _from, _to in connections:\n",
    "            graph[_from].append(_to)\n",
    "            graph[_to].append(-1 * _from)\n",
    "        \n",
    "        visted = [False] * n\n",
    "        print(visted)\n",
    "        def dfs(_from):\n",
    "            visted[_from] = True\n",
    "            for to in graph[_from]:\n",
    "                if not visted[abs(to)]:\n",
    "                    if to > 0:\n",
    "                        self.res = self.res + 1\n",
    "                    else:\n",
    "                        self.res = self.res + 0\n",
    "                    dfs(abs(to))\n",
    "        dfs(0)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        count = 0\n",
    "        visited = [False] * n\n",
    "        def build_graph(n, connections):\n",
    "            graph = [[] for _ in range(n)]\n",
    "            for i in connections:\n",
    "                graph[i[0]].append(i[1])\n",
    "                graph[i[1]].append(-i[0])\n",
    "            return graph\n",
    "        \n",
    "        def dfs(graph, visited, city):\n",
    "            visited[city] = True\n",
    "            for i in graph[city]:\n",
    "                if not visited[abs(i)]:\n",
    "                    if i > 0:\n",
    "                        nonlocal count\n",
    "                        count += 1\n",
    "                    dfs(graph, visited, abs(i))\n",
    "        \n",
    "        graph = build_graph(n, connections)\n",
    "        print(graph)\n",
    "        dfs(graph, visited, 0)\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        fake = [[] for _ in range(n)]\n",
    "        vis = [False] * n\n",
    "\n",
    "        for a, b in connections:\n",
    "            g[b].append(a)\n",
    "            fake[a].append(b)\n",
    "        res = 0\n",
    "        def dfs(node):\n",
    "            nonlocal res\n",
    "            if vis[node]:\n",
    "                return \n",
    "            vis[node] = True\n",
    "\n",
    "            for ch in g[node]:\n",
    "                if not vis[ch]:\n",
    "                    dfs(ch)\n",
    "\n",
    "            for ch in fake[node]:\n",
    "                if not vis[ch]:\n",
    "                    dfs(ch)\n",
    "                    res += 1\n",
    "\n",
    "        dfs(0)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    count = 0\n",
    "    visited = set()\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        graph = []\n",
    "        self.count = 0\n",
    "        self.visited = set()\n",
    "        for i in range(n):\n",
    "            graph.append([])\n",
    "        for connection in connections:\n",
    "            # print(connection[0], connection[1])\n",
    "            graph[connection[0]].append(connection[1])\n",
    "            graph[connection[1]].append(-connection[0])\n",
    "        # print(graph)\n",
    "        self.dfs(graph, 0)\n",
    "        return self.count\n",
    "\n",
    "    def dfs(self, graph, vertex):\n",
    "        #print(vertex)\n",
    "        #print(self.visited)\n",
    "        if vertex not in self.visited:\n",
    "            self.visited.add(vertex)\n",
    "            for neighbor in graph[vertex]:\n",
    "                # print(str(vertex)+\" \"+str(neighbor))\n",
    "                if abs(neighbor) not in self.visited:\n",
    "                    if neighbor > 0:\n",
    "                        self.count = self.count + 1\n",
    "                    self.dfs(graph, abs(neighbor))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        # 根据conection,构建无向图，构成树，然后从0点出发，如果g[u][v]存在，cnt+=0,否则，cnt+=1\n",
    "        g=[list() for _ in range(n)]\n",
    "        visited=set()\n",
    "        for u,v in connections:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "            visited.add((u,v))\n",
    "        def dfs(x,f):\n",
    "            nonlocal cnt\n",
    "            for y in g[x]:\n",
    "                if y==f:continue \n",
    "                if (x,y) in visited:cnt+=1\n",
    "                dfs(y,x)\n",
    "        cnt=0\n",
    "        dfs(0,-1)\n",
    "        return cnt      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        self.hmap = {}\n",
    "        for i, (a, b) in enumerate(connections):\n",
    "            self.hmap.setdefault(a, []).append(i)\n",
    "            self.hmap.setdefault(b, []).append(i)\n",
    "        self.n_routes = 0\n",
    "        self.visited = [0] * n\n",
    "        self.explore(0, connections)\n",
    "        return self.n_routes\n",
    "        \n",
    "    def explore(self, v, connections):\n",
    "        for i in self.hmap[v]:\n",
    "            if self.visited[i]:\n",
    "                continue\n",
    "            self.visited[i] = True\n",
    "            pair = connections[i]\n",
    "            if pair[0] == v:\n",
    "                self.n_routes += 1\n",
    "                u = pair[1]\n",
    "            else:\n",
    "                u = pair[0]\n",
    "            self.explore(u, connections)\n",
    "\n",
    "\n",
    "   \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        \n",
    "        vis = set()\n",
    "        g = [[] for _ in range(n)]\n",
    "        gr = [[] for _ in range(n)]\n",
    "        for a,b in connections:\n",
    "            g[a].append(b)\n",
    "            gr[b].append(a)\n",
    "\n",
    "        ans = 0\n",
    "        def dfs(v):\n",
    "            nonlocal ans\n",
    "            if v in vis:\n",
    "                return\n",
    "            vis.add(v)\n",
    "            for x in g[v]:\n",
    "                if x not in vis:\n",
    "                    ans += 1\n",
    "                    dfs(x)\n",
    "            for x in gr[v]:\n",
    "                if x not in vis:\n",
    "                    dfs(x)\n",
    "        dfs(0)\n",
    "        return ans\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        ch=[[] for _ in range(n)]\n",
    "        for u,v in connections:\n",
    "            ch[u].append((v,0))\n",
    "            ch[v].append((u,1))\n",
    "        res=0\n",
    "        def dfs(u,pa,typ):\n",
    "            nonlocal res\n",
    "            if not typ: res+=1\n",
    "            for v,t in ch[u]:\n",
    "                if v!=pa: dfs(v,u,t)\n",
    "        dfs(0,0,1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        degree = [[] for _ in range(n)]\n",
    "        odegree = [[] for _ in range(n)]\n",
    "        for a,b in connections:\n",
    "            degree[a].append(b)\n",
    "            degree[b].append(a)\n",
    "            odegree[a].append(b)\n",
    "        v = set([0])\n",
    "        ans = 0\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            for j in degree[i]:\n",
    "                if j not in v:\n",
    "                    v.add(j)\n",
    "                    if j in odegree[i]:\n",
    "                        ans += 1 \n",
    "                    dfs(j)\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        E = [[] for _ in range(n)]\n",
    "        for i, j in connections:\n",
    "            E[i].append([j, 1])\n",
    "            E[j].append([i, 0])\n",
    "        def DFS(visited: List[int], i: int) -> int:\n",
    "            if visited[i]: return 0\n",
    "            num = 0\n",
    "            visited[i] = True\n",
    "            for j, k in E[i]:\n",
    "                if not visited[j]: num += DFS(visited, j) + k\n",
    "            return num\n",
    "        return DFS([False] * n, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for a, b in connections:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        \n",
    "        connections = set([(x, y) for x, y in connections])\n",
    "        \n",
    "        # dfs\n",
    "        ret = 0\n",
    "        visited = set()\n",
    "        def dfs(i):\n",
    "            nonlocal ret\n",
    "            visited.add(i)\n",
    "            for j in graph[i]:\n",
    "                if j not in visited:\n",
    "                    if (i, j) in connections: ret += 1\n",
    "                    dfs(j)\n",
    "        \n",
    "        dfs(0)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "\n",
    "        graph=[[]for _ in range(n)]\n",
    "        visit=[0 for _ in range(n)]\n",
    "        for edge in connections:\n",
    "            graph[edge[0]].append([edge[1],1])\n",
    "            graph[edge[1]].append([edge[0],0])\n",
    "        def dfs(s:int)-> int:\n",
    "            visit[s]=1\n",
    "            ans=0\n",
    "            for node in graph[s]:\n",
    "                \n",
    "                    v=node[0]\n",
    "                    flag=node[1]\n",
    "                    if visit[v]:\n",
    "                        continue\n",
    "                    \n",
    "                    if flag==1:\n",
    "                        ans=ans+1\n",
    "                    ans+=dfs(v)\n",
    "            return ans\n",
    "\n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.cnt = 0\n",
    "\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        tree = [[] for i in range(n)]\n",
    "        for i in range(n - 1):\n",
    "            tree[connections[i][0]].append((connections[i][1], 1))\n",
    "            tree[connections[i][1]].append((connections[i][0], -1))\n",
    "        self.dfs(tree, 0, set())\n",
    "        return self.cnt\n",
    "\n",
    "    def dfs(self, tree: List[List[Tuple[int, int]]], node_index, used: set):\n",
    "        node = tree[node_index]\n",
    "        used.add(node_index)\n",
    "        for i in range(len(node)):\n",
    "            if node[i][0] in used:\n",
    "                continue\n",
    "            if node[i][1] == 1:\n",
    "                self.cnt += 1\n",
    "            self.dfs(tree, node[i][0], used)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        self.adjtable = collections.defaultdict(list)\n",
    "        for a, b in connections:\n",
    "            self.adjtable[a].append((b, True))\n",
    "            self.adjtable[b].append((a, False))\n",
    "        self.res = 0\n",
    "        self.dfs(0, -1)\n",
    "        return self.res\n",
    "        \n",
    "        \n",
    "\n",
    "    def dfs(self, city, prev):\n",
    "        for route in self.adjtable[city]:\n",
    "            if route[0] != prev:\n",
    "                if route[1]:\n",
    "                    self.res += route[1]\n",
    "                self.dfs(route[0], city)\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        edges = set()\n",
    "\n",
    "        # 构建图和边集合\n",
    "        for edge in connections:\n",
    "            a, b = edge\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "            edges.add((a, b))\n",
    "\n",
    "        # 深度优先搜索\n",
    "        def dfs(node, parent):\n",
    "            nonlocal result\n",
    "            for neighbor in graph[node]:\n",
    "                if neighbor == parent:\n",
    "                    continue\n",
    "                if (node, neighbor) in edges:\n",
    "                    result += 1\n",
    "                dfs(neighbor, node)\n",
    "\n",
    "        result = 0\n",
    "        dfs(0, -1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        d=defaultdict(list)\n",
    "        for a,b in connections:\n",
    "            d[a].append((b,1))\n",
    "            d[b].append((a,0))\n",
    "        #print(d)\n",
    "        def dfs(fa,node):\n",
    "            ret=0\n",
    "            for son,w in d[node]:\n",
    "                if son!=fa:\n",
    "                    ret+=w+dfs(node,son)\n",
    "            #print(ret,node)\n",
    "            return ret\n",
    "        return dfs(-1,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        d = defaultdict(list)\n",
    "        d_c = Counter(tuple(connection) for connection in connections)\n",
    "        ans = 0\n",
    "        # vis = [False] * n\n",
    "        #构建图\n",
    "        for x, y in connections:\n",
    "            d[x].append(y)\n",
    "            d[y].append(x)\n",
    "        def dfs(x):\n",
    "            nonlocal ans\n",
    "            for v in d[x]:\n",
    "                if v not in vis:\n",
    "                    vis.add(v)\n",
    "                    if (x, v) in d_c:\n",
    "                        ans += 1\n",
    "                    dfs(v)\n",
    "        \n",
    "        vis = set()\n",
    "        vis.add(0)\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        mp = dict()\n",
    "        for c in connections:\n",
    "            if c[1] not in mp:\n",
    "                mp[c[1]] = [(c[0], 0)]\n",
    "            else:\n",
    "                mp[c[1]].append((c[0], 0))\n",
    "            \n",
    "            if c[0] not in mp:\n",
    "                mp[c[0]] = [(c[1], 1)]\n",
    "            else:\n",
    "                mp[c[0]].append((c[1], 1))\n",
    "        \n",
    "        res = 0\n",
    "        visited = [0]*n\n",
    "        def dfs(idx):\n",
    "            nonlocal res\n",
    "            visited[idx]=1\n",
    "\n",
    "            for nb in mp[idx]:\n",
    "                if visited[nb[0]]: continue\n",
    "\n",
    "                dfs(nb[0])\n",
    "                if nb[1]==1:\n",
    "                    res += 1\n",
    "\n",
    "        dfs(0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n",
    "        g = collections.defaultdict(list)\n",
    "        edges = set()\n",
    "\n",
    "        for u, v in connections:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "            edges.add((u, v))\n",
    "\n",
    "        visited = {0}\n",
    "        self.ans = 0        \n",
    "        def dfs(src):\n",
    "            for nb in g[src]:\n",
    "                if nb not in visited:\n",
    "                    visited.add(nb)\n",
    "                    self.ans += (src, nb) in edges\n",
    "                    dfs(nb)\n",
    "        dfs(0)\n",
    "        \n",
    "        return self.ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
